# 创建单向链表

# 创建Node类
class Node:
    def __init__(self, data):
        self.data = data  # 表示对应的元素值
        self.next = None  # 表示下一个链接的链点


# 创建Linked_List类
class Linked_List:
    def __init__(self, head=None):
        self.head = head

    # append方法
    def append(self, new_element):
        # 将头部结点指向临时变量temp
        temp = self.head
        # 当头部结点存在时
        if self.head:
            # 循环遍历到链表最后一个元素
            while temp.next:  # 如果后面一直有元素
                temp = temp.next  # 则不断把值赋给临时变量temp
            temp.next = new_element  # 当循环退出，即到了最后一个元素，则把新元素插入到最后并把下一节点指向新元素
        # 头部结点不存在，即空链表，这插入的元素作为头部结点
        else:
            self.head = new_element

    # is_empty方法
    def is_empty(self):
        """
        判定链表是否为空
        :return: True or False
        """
        return not self.head

    # 获取链表长度get_length()
    def get_length(self):
        """
        获取链表的长度
        :return: length
        """
        temp = self.head
        length = 0

        while temp is not None:
            length = length + 1
            temp = temp.next
        return length

    # insert插入函数
    def insert(self, position, new_element):
        """
        在链表中插入元素
        :param position: 插入的位置
        :param new_element: 插入的元素
        :return:
        """
        # 判断给定的position是否合法
        if position < 0 or position > self.get_length():
            raise IndexError("insert插入时，key值超出了范围")
        # 把头结点指向temp
        temp = self.head
        # 当插入位置为链首时，将插入元素的next属性指向老的头结点，并将新的元素赋值给头结点
        if position == 0:
            new_element.next = temp
            self.head = new_element
            # new_element.next, self.head = temp, new_element
            return
        # 当插入位置不是链首时
        i = 0
        # 遍历找到索引值为position的结点后，在其后面插入新元素
        while i < position:
            pre = temp
            temp = temp.next
            i += 1
        pre.next = new_element
        new_element.next = temp

    # 删除元素
    def remove(self, position):
        # 判断给定的索引值是否合法
        if position < 0 or position > self.get_length() - 1:
            raise IndexError("删除元素的索引超出范围")

        i = 0
        temp = self.head
        # 只有当链表不为空的时候才能执行删除操作
        while temp is not None:
            if position == 0:
                # 头结点的下一个结点作为新的头结点
                self.head = temp.next
                # 原来的头结点置为空
                temp.next = None
                return

            # 循环遍历结点，pre:前结点
            pre = temp
            temp = temp.next
            i += 1
            if i == position:
                pre.next = temp.next
                temp.next = None
                return

    # 打印链表
    def print_list(self):
        print("linked_list: ")
        temp = self.head
        while temp is not None:
            print(temp.data)
            temp = temp.next

    # 链表反转
    def reverse(self):
        pre = None
        temp = self.head
        while temp:
            next_node = temp.next
            temp.next = pre
            pre = temp
            temp = next_node
        self.head = pre

    # 列表转链表
    def init_list(self, data_list):
        # 列表第一个元素作为链表头结点
        self.head = Node(data_list[0])
        temp = self.head
        for i in data_list[1:]:
            node = data_list[i]
            temp.next = node
            temp = temp.next

